package com.zz.util;

import com.zz.node.Node;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class NodeUtil {
    private static Set<Node> set = new HashSet<Node>();

    /**
     * 判断
     *
     * @param node
     */
    public static void forNode(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.data);
        forNode(node.next);
    }

    /**
     * 使用Set集合判断链表是否有环
     *
     * @param node
     * @return
     */
    public static boolean repoNode(Node node) {
        if (node == null) {
            return false;
        }
        if (!set.add(node)) {
            return true;
        }
        return repoNode(node.next);
    }

    /**
     * 快慢指针判断链表是否有环
     *
     * @param node
     * @return
     */
    public static boolean repoQuitNode(Node node) {
        Node slow = node; //慢指针
        Node quit = node; //快指针
        Node first = node;
        while (true) {
            if (quit == null || quit.next == null || quit.next.next == null) {
                return false;
            }
            quit = quit.next.next;
            slow = slow.next;
            if (quit == slow) {
                return true;
            }
        }
    }

    /**
     * 漫画算法书中：快慢指针判断链表是否有环
     *
     * @param head
     * @return
     */
    public static boolean repoQuitNodeCartoon(Node head) {
        Node slow = head; //慢指针
        Node quit = head; //快指针
        while (quit != null || quit.next != null) {
            quit = quit.next.next;
            slow = slow.next;
            if (quit == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 快慢指针判断循环链表中环的长度
     * 第一次相遇后，快指针不动，慢指针动，第二次相遇判断慢指针动了多少次
     * @param head
     * @return
     */
    public static int repoQuitNodeSize(Node head) {
        Node slow = head; //慢指针
        Node quit = head; //快指针
        while (quit != null || quit.next != null) {
            quit = quit.next.next;
            slow = slow.next;
            if (quit == slow) {
                int i = 0;
                //i==0代表第一次还没走，所以放行
                while (quit != slow || i == 0) {
                    slow = slow.next;
                    i++;
                }
                return i;
            }
        }
        return 0;
    }

    /**
     * 快慢指针判断循环链表中环的长度
     * 直接判断快慢指针第一次相遇到第二次相遇中间循环了多少次，也就是快指针过程中多跑了一圈
     * @param head
     * @return
     */
    public static int repoQuitNodeSizeCartoon(Node head) {
        Node slow = head; //慢指针
        Node quit = head; //快指针
        int i = 0;
        boolean flag = true;
        while (quit != null || quit.next != null) {
            quit = quit.next.next;
            slow = slow.next;
            i++;
            if (quit == slow) {
                flag = !flag;
                if (flag) {
                    return i;
                }
                i = 0;
            }
        }
        return 0;
    }

    /**
     * 漫画算法书中：快慢指针找出入环点
     *
     * @param head
     * @return
     */
    public static Node repoQuitFirstNodeCartoon(Node head) {
        Node slow = head; //慢指针
        Node quit = head; //快指针
        while (quit != null || quit.next != null) {
            quit = quit.next.next;
            slow = slow.next;
            if (quit == slow) {
                slow = head;
                while (slow != quit){
                    quit = quit.next;
                    slow = slow.next;
                }
                //以上循环结束后，再相碰则就是入环点的位置
                return quit;
            }
        }
        return null;
    }
}
